package com.example.algorithm.backtrcaking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/12
 * 组合数三
 */
public class Combination3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> listList = new ArrayList<>();
        trackBack(list,listList,k,n,1,0);
        return listList;
    }

    private void trackBack(List<Integer> list, List<List<Integer>> listList, int k, int n, int startIndex,int sum) {

        if(sum==n&&list.size()==k) {
            listList.add(new ArrayList<>(list));
            return;
        } else if(sum!=n&&list.size()==k) {
            return;
        }

        for(int i=startIndex;i<=10-(k-list.size());i++)
        {
            list.add(i);
            sum=sum+i;
            trackBack(list,listList,k,n,i+1,sum);
            int len=list.size()-1;
            sum-=list.get(len);
            list.remove(len);
        }

    }

    public static void main(String[] args) {
        Combination3 combination3 = new Combination3();
        List<List<Integer>> listList = combination3.combinationSum3(2, 18);
        listList.stream().forEach(System.out::println);
    }
}
